package org.laizili.solution.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/range-sum-query-mutable/">307. 区域和检索-数组可修改</a>
 * <p>
 * tags: 分治; 线段树；
 * </p>
 */
public class Problem307 {
    // solution 1: 分块处理
    private static class NumArray {
        private int[] nums;
        private int len;
        private int bulkSize;
        private int[] bulkSum;

        public NumArray(int[] nums) {
            this.nums = nums;
            this.len = nums.length;
            this.bulkSize = (int) Math.sqrt(len);
            int bulkCount = (int) Math.ceil(((double) len) / bulkSize);
            int idx = 0;
            bulkSum = new int[bulkCount];
            while (idx < bulkCount) {
                int sum = 0;
                int lowBounds = idx * bulkSize;
                for (int i = lowBounds; i < len && i < lowBounds + bulkSize; i++) {
                    sum += nums[i];
                }
                bulkSum[idx++] = sum;
            }
        }

        public void update(int index, int val) {
            int blukIdx = index / bulkSize;
            bulkSum[blukIdx] += val - nums[index];
            nums[index] = val;
        }

        public int sumRange(int left, int right) {
            // sumRange [left, right]
            int leftBulkIdx = left / bulkSize;
            int leftBulkSub = left % bulkSize;
            int rightBulkIdx = right / bulkSize;
            int rightBulkSub = right % bulkSize;
            if (leftBulkIdx == rightBulkIdx) {
                int sum = 0;
                for (int i = left; i <= right; i++) {
                    sum += nums[i];
                }
                return sum;
            } else {
                int sum1 = 0;
                int leftLowerBound = leftBulkIdx * bulkSize;
                int leftUpperBound = Math.min(len, leftLowerBound + leftBulkSub);
                for (int i = leftLowerBound; i < leftUpperBound; i++) {
                    sum1 += nums[i];
                }
                int sum2 = 0;
                int rightLowerBound = rightBulkIdx * bulkSize + rightBulkSub + 1;
                int rightUpperBound = Math.min(len, rightBulkIdx * bulkSize + bulkSize);
                for (int i = rightLowerBound; i < len && i < rightUpperBound; i++) {
                    sum2 += nums[i];
                }
                int sum3 = 0;
                for (int i = leftBulkIdx; i <= rightBulkIdx; i++) {
                    sum3 += bulkSum[i];
                }
                return sum3 - sum1 - sum2;
            }
        }
    }
}
